﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。
//
//（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int add(int x)
//{
//	if (x<2)
//	{
//		return 0;
//	}
//	int i = 0;
//	for (i = 2; i*i <= x; i++)
//	{
//		if (x%i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//int countPrimeSetBits(int left, int right){
//	int count = 0;
//	int tmp = 0;
//	int i = 0;
//	int n = 0;
//	for (i = left; i <= right; i++)
//	{
//		n = i;
//		tmp = 0;
//		while (n)
//		{
//			tmp += n % 2;
//			n /= 2;
//		}
//		count += add(tmp);
//	}
//	return count;
//}







//给你一个整数数组 A，请你给数组中的每个元素 A[i] 都加上一个任意数字 x （ - K <= x <= K），从而得到一个新数组 B 。
//
//返回数组 B 的最大值和最小值之间可能存在的最小差值。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/smallest-range-i
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int smallestRangeI(int* nums, int numsSize, int k){
//	int mid = nums[0];
//	int max = nums[0];
//	int i = 0;
//	int count = 0;
//	for (i = 1; i<numsSize; i++)
//	{
//		mid = mid<nums[i] ? mid : nums[i];
//		max = max>nums[i] ? max : nums[i];
//	}
//	count = max - mid;
//	if (count <= 2 * k)
//	{
//		return 0;
//	}
//	return count - 2 * k;
//}








给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。

//如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。
//
//源数组中可能存在 重复项 。
//
//注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i + x) % A.length] ，其中 % 为取余运算。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/check-if-array-is-sorted-and-rotated
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool check(int* nums, int numsSize){
//	int a = 0;
//	int i = 0;
//	for (i = 1; i <= numsSize; i++)
//	{
//		if (nums[i%numsSize]<nums[i - 1] && ++a>1)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}








//你和你的朋友，两个人一起玩 Nim 游戏：
//
//桌子上有一堆石头。
//你们轮流进行自己的回合，你作为先手。
//每一回合，轮到的人拿掉 1 - 3 块石头。
//拿掉最后一块石头的人就是获胜者。
//假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/nim-game
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool canWinNim(int n){
//	if (n % 4 == 0)
//	{
//		return 0;
//	}
//	return 1;
//}








//配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）。
//int exchangeBits(int num){
//	int a = 0x55555555;
//	int b = 0x2aaaaaaa;
//	a = num&a;
//	b = num&b;
//	a <<= 1;
//	b >>= 1;
//	return a | b;
//}







//给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。
//
//如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/toeplitz-matrix
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool isToeplitzMatrix(int** matrix, int matrixSize, int* matrixColSize){
//	int i = 0;
//	int j = 0;
//	for (i = 1; i<matrixSize; i++)
//	{
//		for (j = 1; j<*matrixColSize; j++)
//		{
//			if (matrix[i][j] != matrix[i - 1][j - 1])
//			{
//				return 0;
//			}
//		}
//	}
//	return 1;
//
//}







//给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
//网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
//岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/island-perimeter
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int islandPerimeter(int** grid, int gridSize, int* gridColSize){
//	int count = 0;
//	int i = 0;
//	int j = 0;
//	for (i = 0; i<gridSize; i++)
//	{
//		for (j = 0; j<*gridColSize; j++)
//		{
//			if (grid[i][j])
//			{
//				count += 4;
//				if (i>0)
//				{
//					count -= grid[i - 1][j];
//				}
//				if (i<gridSize - 1)
//				{
//					count -= grid[i + 1][j];
//				}
//				if (j>0)
//				{
//					count -= grid[i][j - 1];
//				}
//				if (j<*gridColSize - 1)
//				{
//					count -= grid[i][j + 1];
//				}
//			}
//		}
//	}
//	return count;
//}








//学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
//餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：
//
//如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
//否则，这名学生会 放弃这个三明治 并回到队列的尾部。
//这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
//
//给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/number-of-students-unable-to-eat-lunch
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int countStudents(int* students, int studentsSize, int* sandwiches, int sandwichesSize){
//	int a[2] = { 0 };
//	int i = 0;
//	for (i = 0; i<studentsSize; i++)
//	{
//		a[students[i]]++;
//	}
//	for (i = 0; i<sandwichesSize; i++)
//	{
//		if (a[sandwiches[i]] == 0)
//		{
//			break;
//		}
//		--a[sandwiches[i]];
//	}
//	return a[1] + a[0];
//}








/**给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中：

第一行由字符 "qwertyuiop" 组成。
第二行由字符 "asdfghjkl" 组成。
第三行由字符 "zxcvbnm" 组成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/keyboard-row
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* Note: The returned array must be malloced, assume caller calls free().
*/
//int cmp(char *s)
//{
//	char *s1 = "qwertyuiopQWERTYUIOP";
//	char *s2 = "asdfghjklASDFGHJKL";
//	char *s3 = "zxcvbnmZXCVBNM";
//	int i = 0;
//	int len = strlen(s);
//	if (strchr(s1, s[0]))
//	{
//		for (i = 1; i<len; i++)
//		{
//			if (strchr(s1, s[i]) == 0)
//			{
//				return 0;
//			}
//		}
//	}
//	if (strchr(s2, s[0]))
//	{
//		for (i = 1; i<len; i++)
//		{
//			if (strchr(s2, s[i]) == 0)
//			{
//				return 0;
//			}
//		}
//	}
//	if (strchr(s3, s[0]))
//	{
//		for (i = 1; i<len; i++)
//		{
//			if (strchr(s3, s[i]) == 0)
//			{
//				return 0;
//			}
//		}
//	}
//	return 1;
//}
//char ** findWords(char ** words, int wordsSize, int* returnSize){
//	char**a = (char**)malloc(sizeof(char*)*wordsSize);
//	*returnSize = 0;
//	int i = 0;
//	int j = 0;
//	for (i = 0; i<wordsSize; i++)
//	{
//		if (cmp(words[i]) == 1)
//		{
//			a[j++] = words[i];
//		}
//	}
//	*returnSize = j;
//	return a;
//}









//给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
//
//「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 | arr1[i] - arr2[j] | <= d 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/find-the-distance-value-between-two-arrays
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int findTheDistanceValue(int* arr1, int arr1Size, int* arr2, int arr2Size, int d){
//	int max = 0;
//	int mid = 0;
//	int count = 0;
//	int falg = 0;
//	int i = 0;
//	int j = 0;
//	for (i = 0; i<arr1Size; i++)
//	{
//		falg = 0;
//		for (j = 0; j<arr2Size; j++)
//		{
//			max = arr1[i]>arr2[j] ? arr1[i] : arr2[j];
//			mid = arr1[i]<arr2[j] ? arr1[i] : arr2[j];
//			if (max - mid <= d)
//			{
//				falg = 1;
//				break;
//			}
//		}
//		if (falg == 0)
//		{
//			count++;
//		}
//	}
//	return count;
//}